/* Author: Marco Tezzele */

/* Dijkstra's algorithm that solves the single-source shortest path problem for
 * a graph with nonnegative edge path costs. */

#include <stdio.h>

#define NODES_NUMBER        4  // Number of nodes
#define UNREACHABLE_BOUND	100 // Intero massimo per inizializzare distanceVector
#define START_NODE			0
#define ARRIVAL_NODE   		3

void readWeights(int weights[NODES_NUMBER][NODES_NUMBER], char fileName[]) {
	FILE * fileWeights = fopen("weights.txt", "r");
		if (fileWeights == NULL) {
			printf("Error occurs opening the weights file.\n");
			return;
		}
		// Read weights file.
		int i, j;
		for (i = 0; i < NODES_NUMBER; i++) {
			for (j = 0; j < NODES_NUMBER; j++) {
				fscanf(fileWeights, "%d", &weights[i][j]);
			}
		}
		fclose(fileWeights);
}

int dijkstra(char weightsFile[]) {

	int i, j;
	int distances[NODES_NUMBER];     // distances vector
	int minPaths[NODES_NUMBER];     // min paths vector
	int visitedNodes[NODES_NUMBER]; // 0 if the node is unvisited, 1 otherwise
	int reversePaths[NODES_NUMBER]; // vector with the reverse min path

	int weights[NODES_NUMBER][NODES_NUMBER]; // weights matrix

	readWeights(weights, weightsFile);

	// Initialization
	for (i = 0; i < NODES_NUMBER; i++) {
		distances[i] = UNREACHABLE_BOUND; // Not reachable distance.
		visitedNodes[i] = 0;
	}

	distances[START_NODE] = 0;
	minPaths[START_NODE] = -1;

	int foundPath = 0;
	for (;;) {
		// Search for the unvisited node with min distance
		int m = UNREACHABLE_BOUND;
		int j;
		for (i = 0; i < NODES_NUMBER; i++) {
			if (!visitedNodes[i] && distances[i] <= m) {
				j = i;
				m = distances[j];
			}
		}
		visitedNodes[j] = 1;

		if (j == ARRIVAL_NODE) { // Arrival node reached or if it is not reachable.
			foundPath = 1;
			break;
		}
		if (m == UNREACHABLE_BOUND) {
			break;
		}

		// Update of distances and min paths: if node i is reachable from node j and the cost of the path
		// through j is less than the direct one to i, than the passage through j is forced.
		for (i = 0; i < NODES_NUMBER; ++i) {
			if (weights[j][i] > 0
			        && distances[i] > distances[j] + weights[j][i]) {
				distances[i] = distances[j] + weights[j][i];
				minPaths[i] = j;
			}
		}

	}

	/* Memorizziamo l'effettivo percorso minimo ricostruendo all'indietro minPathsVector */
	j = 0;
	reversePaths[j] = minPaths[NODES_NUMBER - 1];
	while (reversePaths[j] > -1) {
		reversePaths[j + 1] = minPaths[reversePaths[j]];
		j++;
	}

	/* Stampo la distanza di tutti i nodi da START_NODE */
	printf("DIJKSTRA ALGHORITM:\ndistances vector: ");
	if (foundPath == 0) {
		printf("There is no path to reach %d from %d is! :(", ARRIVAL_NODE,
		        START_NODE);
		return 0;
	}
	for (i = 0; i < NODES_NUMBER; i++) {
		printf("%d ", distances[i]);
	}
	printf("\n");
	/* Stampo il vettore dei percorsi minimi partendo da START_NODE */
	printf("min paths vector: ");
	for (i = 0; i < NODES_NUMBER; i++) {
		printf("%d ", minPaths[i]);
	}
	printf("\n");
	printf("Min path to reach node %d from node %d is:\n", ARRIVAL_NODE,
	        START_NODE);
	for (i = j - 1; i >= 0; --i) {
		printf("%d -> ", reversePaths[i]);
	}
	printf("%d\n", ARRIVAL_NODE);
	printf("and the cost is: %d\n", distances[NODES_NUMBER - 1]);

	return distances[NODES_NUMBER - 1];
}

